﻿/*
题目：找两个和为目标值且不重叠的子数组

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // **KEY** 使用 HashMap 记录 和 以及 结束下标
    // **KEY** 使用 dp 来存储 <= i 下标 出现的 最小子数组长度
    int minSumOfLengths(vector<int>& ar, int target) {
        // 这个记录 所有 sum 的结束下标，因为有可能被覆盖，所以还需要一个 dp 数组来存储
        unordered_map<int, int>     mp;         // HashMap<Sum, BeginIndex>
        // 表示 <= i 时，最近出现过的 和为 target 的子数组长度，并且是最短的，后面不会有影响了
        vector<int>                 dp(ar.size());

        mp.emplace(0, -1);
        int res = INT_MAX;
        int sum = 0;
        for (int i = 0; i < ar.size(); i++) {
            // dp[i] 需要继承前面的结果
            dp[i] = i > 0 ? dp[i - 1] : INT_MAX;
            sum += ar[i];
            mp.emplace(sum, i);

            // 是否存在这样的子数组
            if (mp.count(sum - target) == true) {
                int beg = mp[sum - target];
                if (beg >= 0 && dp[beg] != INT_MAX)        // 特殊处理一下
                    res = min(res, i - beg + dp[beg]);

                if (i > 0)  dp[i] = min(dp[i - 1], i - beg);
                else        dp[i] = i - beg;
            }
        }

        return res == INT_MAX ? -1 : res;
    }
};